PsL Monthly 1993 December

home *** CD-ROM | disk | FTP | other *** search

/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / rcs.exe / CACHE.DOC < prev next >

Wrap

Text File | 1992-09-01 | 12.8 KB | 317 lines

A Simple Reentrant Cache System Version 1.0 by Philip J. Erdelsky CompuServe 75746,3411 InterNet 75746.3411@compuserve.com September 1, 1992 PUBLIC DOMAIN -- NO RESTRICTIONS ON USE 1. Introduction --------------- Many applications that use disks tend to read and write the same sectors repeatedly. A technique called caching can make such applications run much faster. With this technique, frequently used sectors are read into memory buffers when the application begins. The application then reads and writes the memory buffers. When the application terminates, the buffers are written to the disk. Since reading and writing memory buffers is much faster than reading or writing disk sectors, the application can run much faster. There are some problems with caching. For example, it can be difficult to determine which sectors will be used frequently. However, the technique is widely used because the improvement is often quite substantial. This cache system is a simple one, designed to be placed between the Reentrant DOS-Compatible File System (RDCF) and a disk driver. A single cache can be used for two or more drives, as long as they all have the same sector size. The cache system is not reentrant with respect to different drives in this case, so access to it must be serialized. The cache system can handle as many separate caches as available memory permits. It is fully reentrant with respect to different caches. However, separate caches may not access the same drive. The cache system calls the standard C functions malloc() and free() when a cache is being initialized or freed, so reentrancy of those functions is required at those times. However, it does no memory allocation or deallocation at other times. The number of sectors in the cache and the size of each sector are determined at run time and need not be the same for all caches. The only limit to the number of sectors in the cache is available memory. A cached sector need not correspond to a single sector on disk, but it must be treated as such by functions that call and are called by the cache system. Each cache can handle up to 32,768 drives, numbered from 0 to 32,767, and up to 65,536 sectors on each drive, numbered from 0 to 65,535. The use of larger numbers will produce numeric overflow and catastrophic failure. Drive numbers and sector numbers need not be consecutive. No cache system can be optimal in every conceivable case, no matter how cleverly it is programmed. This cache system uses one of the simplest methods, and it is apparently adequate for some purposes. You are welcome to make your own improvements, but you must assume responsibility for the results if you make a mistake. In this cache system, each cached sector may exist in any of three states: (1) An EMPTY sector bears no relation to any disk sector. (2) A CLEAN sector contains the same data as the corresponding disk sector. (3) A DIRTY sector contains data which is to be written to the corresponding disk sector but has not yet been written. The cache system attempts to keep each sector in the cache as long as it can, and it uses the least-recently-used criterion when cached sectors must be reused. The process is explained in greater detail in Section 4. The source code for the cache system consists of the file CACHE.C and the header file CACHE.H. The latter should be #included in any source file that calls on the cache system, because it contains prototypes for all cache functions and other necessary information. The cache system calls on the following standard C functions: malloc() free() memcpy() To prevent identifier conflicts, all publicly defined identifiers in the cache system begin with the characters "cache", "CACHE" or "_CACHE". 2. How the Cache Reads and Writes a Sector ------------------------------------------ The cache system does not read or write the disk directly. You must provide it with a pointer to a function that you have written for your implementation. The cache system then calls this function whenever it needs to read or write a disk sector. The format of the function call is as follows: e = (*drive_access)(write, drive, sector, buffer); int write; nonzero (true) for a write operation; zero (false) for a read operation unsigned drive; drive to be read or written unsigned sector; sector to be read or written void *buffer; address of memory buffer to receive or supply data unsigned e; zero for a successful operation, or an implementation-defined nonzero error code When the cache receives a nonzero value from this function, it aborts the cache operation and returns the value as its own functional value. The cache control block contains the drive and sector numbers of the offending operation in the members error_drive and error_sector, respectively. This is especially helpful for diagnostic purpose, because the error almost always occurs in a sector other than the one currently being accessed by the application. 3. Creating and Initializing a Cache ------------------------------------ The following function call creates and initializes a cache: q = cache_initialize(drive_access, number_of_sectors, sector_size); unsigned (*drive_access)(); pointer to function called by cache to read or write a sector unsigned number_of_sectors; number of sectors to be stored in cache (must be at least 1) unsigned sector_size; number of bytes in a sector (1-65,535) struct cache *q; pointer to cache control block, or NULL if there was insufficient memory The function calls on malloc() to allocate memory for the cache storage. If malloc() returns NULL at any point in the process, the function calls free() to release any memory that it has allocated and returns a NULL pointer. Otherwise, it returns a pointer that can be passed to other cache functions. It marks all sectors in the cache as empty. A sector size near the upper limit of 65,535 may cause numeric overflow and catastrophic failure if the implementation does not permit allocation of single objects larger than 65,535 bytes. 4. Reading or Writing Through the Cache --------------------------------------- The heart of the cache system is the following function call: e = cache_access(q, write, drive, sector, buffer); struct cache *q; pointer to cache control block received from cache_initialize() int write; nonzero (true) for a write operation; zero (false) for a read operation unsigned drive; drive to be read or written unsigned sector; sector to be read or written void *buffer; address of memory buffer to receive or supply data unsigned e; zero for a successful operation, or an implementation-defined nonzero error code This function writes or reads the specified sector to or from the specified drive, using the cache as follows: (1) If the specified sector is not already in the cache, a cache sector is assigned to it as follows: (a) If there are still empty sectors in the cache, one of them is assigned to the specified sector. (b) If there are no empty sectors, but there are some clean ones, the least-recently used clean sector is marked as empty and assigned to the specified sector. (c) In other cases, the least-recently used dirty sector is written to disk, marked as empty, and assigned to the specified sector. (2) When reading, (a) If the sector is empty, it is read from the disk and marked as clean. (b) The sector is then copied from the cache to the calling program's buffer. (3) When writing, the calling program's buffer is copied to the cache and the sector is marked as dirty. IT IS NOT WRITTEN TO DISK. (4) The sector is marked as the most recently used. If an error is detected on an actual disk access, this function aborts the operation, puts the drive and sector numbers of the offending sector into q->error_drive and q->error sector, and returns the implementation-defined nonzero error code passed to it by (*drive_access)(). Otherwise, it returns zero. 5. Flushing the Cache --------------------- Before a disk can be changed or removed, the dirty sectors must be written out. The following function call does that, either for a specified drive or for all drives: e = cache_flush(q, drive); struct cache *q; pointer to cache control block received from cache_initialize() int drive; drive to be flushed; if drive<0, all drives are flushed unsigned e; zero for a successful operation, or an implementation-defined nonzero error code If the drive number is nonnegative, this function writes all dirty sectors to the specified drive and marks them as clean. Sectors on other drives are not affected. If the drive number is negative, it writes all dirty sectors to all drives and marks them as clean. The sectors are not written in any specified order, and their usage order is not changed. If an error is detected while writing a sector, this function aborts the operation, puts the drive and sector numbers of the offending sector into q->error_drive and q->error sector, and returns the implementation-defined nonzero error code passed to it by (*drive_access)(). Otherwise, it returns zero. This function is implemented as a macro which generates a call on the function cache_flush_and_or_clear(). 6. Clearing the Cache --------------------- After a disk is changed, the cached sectors on that drive become invalid. The following function call informs the cache system of that fact: cache_clear(q, drive); struct cache *q; pointer to cache control block received from cache_initialize() int drive; drive to be cleared; if drive<0, all drives are cleared If the drive number is nonnegative, this function marks all cached sectors on the specified drive as empty. Sectors on other drives are not affected. If the drive number is negative, it marks all cached sectors on all drives as empty. THIS FUNCTION DOES NOT WRITE THE CACHED SECTORS TO DISK, EVEN IF THEY ARE DIRTY. This function is implemented as a macro which generates a call on the function cache_flush_and_or_clear(). 7. Flushing and Clearing the Cache ---------------------------------- Before a disk can be changed and removed, the dirty sectors must be written out, and the cached sectors on the drive must be marked as invalid. The following function call does that, either for a specified drive or for all drives: e = cache_flush_and_clear(q, drive); struct cache *q; pointer to cache control block received from cache_initialize() int drive; drive to be flushed and cleared; if drive<0, all drives are flushed and cleared unsigned e; zero for a successful operation, or an implementation-defined nonzero error code If the drive number is nonnegative, this function first finds all sectors assigned to the specified drive. It writes the dirty sectors to the specified drive and then marks both clean and dirty sectors as empty. Sectors on other drives are not affected. If the drive number is negative, it does the same thing to all sectors on all drives. The sectors are not written in any specified order. If an error is detected while writing a sector, this function aborts the operation, puts the drive and sector numbers of the offending sector into q->error_drive and q->error sector, and returns the implementation-defined nonzero error code passed to it by (*drive_access)(). Otherwise, it returns zero. This function is equivalent to calls on cache_flush() and cache_clear(), but it is more efficient because it makes only a single pass through the cache. This function is implemented as a macro which generates a call on the function cache_flush_and_or_clear(). 8. Freeing the Cache -------------------- The following function calls free() to release all memory allocated for a cache: cache_free(q); struct cache *q; pointer to cache control block received from cache_initialize()